package q135_candy;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {1, 0 ,2};
        s.candy(a);
    }
    /*
    典型的贪心算法
    这道题⽬⼀定是要确定⼀边之后，再确定另⼀边，例如⽐较每⼀个孩⼦的左边，然后再⽐较右边，如果两边⼀起考虑⼀定会顾此失彼
     */
    public int candy(int[] ratings) {
        int ans = 0;
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        // 先确定右边评分⼤于左边的情况（也就是从前向后遍历）
        // 此时局部最优：只要右边评分⽐左边⼤，右边的孩⼦就多⼀个糖果，全局最优：相邻的孩⼦中，
        // 评分⾼的右孩⼦获得⽐左边孩⼦更多的糖果
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        //  此时就可以开始统计答案 先加入最后一位
        ans += candies[ratings.length - 1];
        // 确定左孩⼦⼤于右孩⼦的情况⼀定要从后向前遍历
        /*
        局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最⼤的糖果数量，保证第i个⼩孩的糖果数量即
        ⼤于左边的也⼤于右边的。全局最优：相邻的孩⼦中，评分⾼的孩⼦获得更多的糖果。
        局部最优可以推出全局最优。
        所以就取candyVec[i + 1] + 1 和 candyVec[i] 最⼤的糖果数量，candyVec[i]只有取最⼤的才能既保持对左边
        candyVec[i - 1]的糖果多，也⽐右边candyVec[i + 1]的糖果多。
         */
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
            ans += candies[i];
        }

        return ans;
    }
}
